{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# Introduction to Graph Algorithms with Networkx\n",
    "\n",
    "## Try me\n",
    " [![Open In Colab](../../_static/colabs_badge.png)](https://colab.research.google.com/github/ffraile/operations-research-notebooks/blob/main/docs/source/MIP/tutorials/Networkx%20Tutorial.ipynb)[![Binder](../../_static/binder_badge.png)](https://mybinder.org/v2/gh/ffraile/operations-research-notebooks/main?labpath=docs%2Fsource%2FMIP%2Ftutorials%2FNetworkx%20Tutorial.ipynb)\n",
    "\n",
    "## Introduction\n",
    "This notebook provides an overview and tutorial of [Networkx](https://networkx.org/), a Python package to create, manipulate, and analyse graphs with an \n",
    "extensive set of algorithms to solve common graph theory problems. \n",
    "Basically, we will use Networkx to build a network model of the network, and present some of the most important algorithms \n",
    "to solve the problems covered in the book, and finally we will see some nice add-ons and tools to draw networks and create \n",
    "networks from other data structures such as open maps!\n",
    "\n",
    "## Requirements\n",
    "\n",
    "You need to install Networkx in your runtime, so make sure you run this script if not already installed. \n",
    "\n",
    "Note that the installation line includes the *extra* option to install additional packages which are useful to work with\n",
    "Networkx."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "!pip install networkx[default,extra]\n",
    "!pip install ipython\n",
    "!pip install pandas"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Instalation\n",
    "We are going to import the package as *nx* in this tutorial:"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "import networkx as nx"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% \n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## The basics\n",
    "### Creating networks\n",
    "We can create different types of graphs with the following constructor functions. Review the definitions in the [Graph theory tutorial](Graph%20theory.ipynb):\n",
    "\n",
    "- ```nx.Graph```: Creates an object representing an undirected graph.\n",
    "- ```nx.DiGraph```: Creates an object representing a directed Graph\n",
    "- ```nx.MultiGraph:``` Creates an object representing a with multiple edges between any pair of nodes\n",
    "- ```nx.MultiDiGrpah:``` Directed graph with multiple edges between any pair of nodes\n",
    "\n",
    "By default, graphs are created without nodes or edges. The simplest way to add edges and nodes is to use the class methods \n",
    " ```add_node``` and ```add_edge```. The former adds the object that is passed as argument as a node of the graph. We can \n",
    "add as a node a string variable, a numeric, or a tuple with several values which are relevant for our \n",
    "application. In fact, we can add any *hashable* object, any object that will not change during the execution of the \n",
    "program. Functions and objects of user-defined classes are also hashable by default. You can find the precise definition \n",
    "of hashable in the [glossary](https://docs.python.org/3/glossary.html), but what is important is that Python can assign \n",
    "a unique identifier to each hashable object, and networkx uses these feature to identify each node of the network. \n",
    "Normally, we will use simple types like strings or integers, with different values for each node. \n",
    "The function ```add_edge``` creates and edge passing between two objects are arguments. If the objects are already in \n",
    "the network, it will create an edge between the two, as long as the type of network allows it (if not, it will raise an \n",
    "exception). If any of the objects passed as arguments are not in the network, the function will also add them as nodes. \n",
    "For instance:"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Create an undirected graph\n",
    "my_first_Graph = nx.Graph()\n",
    "\n",
    "# Add and edge between nodes 1, 2. Automatically creates nodes 1 and 2\n",
    "my_first_Graph.add_edge(1, 2)\n",
    "\n",
    "# Add a third node\n",
    "my_first_Graph.add_node(3)\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "We can add attributes to the edges. We can define as many attributes as we want and pass them as named arguments to the \n",
    "```add_edge``` function, for instance:"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "# add another edge with weight 3 between nodes 2 and 3.\n",
    "my_first_Graph.add_edge(2, 3, weight=3)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "Graph properties describe the structure of the graph, for instance, the list of nodes and edges. Some important properties\n",
    "are:\n",
    "\n",
    "- ```nodes```: Provides a list containing the nodes of the graph. Each element of the list is the object used to add a node.\n",
    "\n",
    "- ```edges```: Provides the list of the edges of the graph. Each edge is represented as a tuple where the first element \n",
    "is the object that represents the origin node and the second element is the object that represents the destination node.\n",
    "\n",
    "- ```adjacency```: The adjacency provides a dictionary containing the information in the adjacency matrix. Normally, \n",
    "the adjacency matrix will be sparse (containing lots of zeroes) and, for the sake of efficiency, networkx represents the \n",
    "adjacency as a dictionary where the node objects are keys and the values are dictionaries with the information of the \n",
    "edges with origin at the key node. The information of the edges are also dictionaries, where each key is the destination \n",
    " node object and the values are dictionaries with the attributes of the edge (see example below).\n",
    "\n",
    "- ```degree```: The degree of each node of the graph is represented as a tuple where the first element is the node object \n",
    "and the second element an integer with the degree of the graph. \n",
    "\n",
    "- ``` size() ```: The size of the graph (integer)\n",
    "- ``` order() ```: The order of the graph (integer)\n",
    "\n",
    "Let`s see these properties with the example above:"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "# The nodes property contains a list of nodes\n",
    "print(my_first_Graph.nodes)\n",
    "\n",
    "# The edges:\n",
    "print(my_first_Graph.edges)\n",
    "\n",
    "# The adjacency:\n",
    "print(my_first_Graph.adj)\n",
    "\n",
    "# Or the order:\n",
    "print(my_first_Graph.order())\n",
    "\n",
    "#Or the size:\n",
    "print(my_first_Graph.size())\n",
    "\n",
    "#Or the degree\n",
    "print(my_first_Graph.degree)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Algorithms\n",
    "Networkx has an extensive library of algorithms to solve graph theory problems, ranging from path algorithms to flow algorithms. The next sections provide practical examples and guidelines to solve common graph theory problems using Networkx.\n",
    "\n",
    "#### Path algorithms\n",
    "It packages several algorithms to compute paths, the shortest paths and path lengths between nodes in a graph. The\n",
    "algorithms work both on directed and undirected graphs. Basically, they all take as arguments the graph, the source and \n",
    "target nodes, and optionally the edge attribute that represents the distance, cost or weight of each edge. If not\n",
    "provided, all edges have a weight equal to one.\n",
    "\n",
    "##### shortest_path\n",
    "Shortest_path computes the shortest paths in the graph. By default, it uses the Dijkstra algorithm, but it is possible \n",
    "to use Bellman-Ford's algorithm using the argument ```method = ‘bellman-ford’```. \n",
    "If only the source node is specified, shortest_path returns a dictionary keyed by targets with the shortest path between \n",
    " the source node and every other node in the network. Conversely, if only the target is specified, it returns a\n",
    " dictionary keyed by sources with the shortest path from every node to the specified target node. If neither the source \n",
    "nor target are specified, it returns a dictionary of dictionaries with all shortest paths from every source and every \n",
    "target node."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Create a directed graph structure: \n",
    "G = nx.DiGraph()\n",
    "\n",
    "G.add_edge(0,1, cost=1700)\n",
    "G.add_edge(0,2, cost=3968)\n",
    "G.add_edge(0,3, cost=7622)\n",
    "G.add_edge(0,4, cost=10970)\n",
    "G.add_edge(1,2, cost=1880)\n",
    "G.add_edge(1,3, cost=1880)\n",
    "G.add_edge(1,4, cost=4652)\n",
    "G.add_edge(2,3, cost=2300)\n",
    "G.add_edge(2,4, cost=4316)\n",
    "G.add_edge(3,4, cost=2720)\n",
    "\n",
    "# Get the shortest path between nodes 0 and 4:\n",
    "g_shortest_paths = nx.shortest_path(G, 0, 4, weight='cost')\n",
    "print(g_shortest_paths)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### minimum_spanning_tree\n",
    "minimum_spanning_tree returns the minimum spanning tree of an undirected graph. Recall that the minimum spanning tree is\n",
    "a sub-graph that connects all the nodes in the graph with the minimum sum of edge weights.\n",
    "If the graph is not connected, the function returns a collection of the minimum spanning trees of each connected sub-graph.\n",
    "This is referred to as a spanning forest.\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "G = nx.Graph()\n",
    "G.add_node(\"a\")\n",
    "G.add_node(\"d\")\n",
    "G.add_edge(\"a\", \"b\", weight=3)\n",
    "G.add_edge(\"a\", \"c\", weight=6)\n",
    "G.add_edge(\"b\", \"d\", weight=1)\n",
    "G.add_edge(\"c\", \"d\", weight=2)\n",
    "T = nx.minimum_spanning_tree(G)\n",
    "print(T.edges)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### Flow algorithms\n",
    "##### maximum_flow\n",
    "maximum_flow finds a maximum flow of a commodity in a directed graph where each node has a 'capacity' attribute that \n",
    "specifies the maximum capacity that the flow can support. It returns the value of the flow and the path that provides \n",
    "the maximum flow in a dictionary keyed with the source and destination nodes. See the example below:\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "G = nx.DiGraph()\n",
    "G.add_edge(\"x\", \"a\", capacity=3.0)\n",
    "G.add_edge(\"x\", \"b\", capacity=1.0)\n",
    "G.add_edge(\"a\", \"c\", capacity=3.0)\n",
    "G.add_edge(\"b\", \"c\", capacity=5.0)\n",
    "G.add_edge(\"b\", \"d\", capacity=4.0)\n",
    "G.add_edge(\"d\", \"e\", capacity=2.0)\n",
    "G.add_edge(\"c\", \"y\", capacity=2.0)\n",
    "G.add_edge(\"e\", \"y\", capacity=3.0)\n",
    "\n",
    "flow_value, flow_dict = nx.maximum_flow(G, \"x\", \"y\")\n",
    "print(flow_value)\n",
    "print(flow_dict)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "##### min_cost_flow\n",
    "G is a directed graph with edge capacity and in which nodes have demand, maximum_flow_value finds a maximum flow from a \n",
    "source node to a destination node, using the node s to node s, using edge attribute ‘capacity’ as edge capacity and node \n",
    "attribute 'demand' as the demand.  negative demand means that the node wants to send flow, a positive demand means that \n",
    "the node want to receive flow. A flow on the digraph G satisfies all demand if the net flow into each node is equal to \n",
    "the demand of that node."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "G = nx.DiGraph()\n",
    "G.add_node(\"a\", demand=-5)\n",
    "G.add_node(\"d\", demand=5)\n",
    "G.add_edge(\"a\", \"b\", weight=3, capacity=4)\n",
    "G.add_edge(\"a\", \"c\", weight=6, capacity=10)\n",
    "G.add_edge(\"b\", \"d\", weight=1, capacity=9)\n",
    "G.add_edge(\"c\", \"d\", weight=2, capacity=5)\n",
    "flowDict = nx.min_cost_flow(G)\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Displaying networks\n",
    "You can draw the graph with the function ```draw(G, pos)```. The function takes a graph as the first argument. \n",
    "The second argument is a tuple with the relative (x, y) coordinates of nodes in the graph. \n",
    "\n",
    "Networkx provides convenient functions to customise the representation of the network:\n",
    "\n",
    "- The function ```draw_networkx_labels``` is used to control the presentation of the node labels (reference [here](https://networkx.org/documentation/stable/reference/generated/networkx.drawing.nx_pylab.draw_networkx_labels.html) \n",
    "- The function ```draw_networkx_nodes```to control the presentation of the nodes (reference here)\n",
    "- The function ```draw_networkx_edge_labels``` to control the edge labels (reference here). \n",
    "\n",
    "See a practical example below:"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "pos = {1: (0, 0), \n",
    "       2: (1, 0),\n",
    "       3: (2, 0)}\n",
    "nx.draw(my_first_Graph, pos)\n",
    "nx.draw_networkx_labels(my_first_Graph, pos)\n",
    "nx.draw_networkx_nodes(my_first_Graph, pos, node_size=600, node_color='#efefef')\n",
    "nx.draw_networkx_edge_labels(my_first_Graph, pos, edge_labels={(1, 2): 0, (2, 3): 3})\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Creating networks from datasets\n",
    "### Add edges from edge list\n",
    "Networkx provides convenient functions and methods to create networks from large data structures. This is necessary to \n",
    "build networks in practical applications. This section covers functions to create graphs from iterables and Pandas data frames.\n",
    "\n",
    "\n",
    "Specifically, The method ```add_edges_from``` adds edges from an array where \n",
    "each element is a tuple (*edge tuple*) with the following elements:\n",
    "\n",
    "- origin node object\n",
    "- destination node object\n",
    "- (optional) dictionary with edge properties\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "my_graph = nx.DiGraph()\n",
    "my_edges = [(1, 2, {\"weight\": 3, \"capacity\": 5}), # adds an edge from node 1, to node 2, with weight 3 and capacity 5\n",
    "            (2, 1, {\"weight\": 2, \"capacity\": 4}),\n",
    "            (2, 3, {\"weight\": 3, \"capacity\": 6}),\n",
    "            (3, 1, {\"weight\": 3, \"capacity\": 6}),\n",
    "            (3, 4, {\"weight\": 2, \"capacity\": 5}),\n",
    "            (4, 3, {\"weight\": 5, \"capacity\": 8}),\n",
    "            (4, 5, {\"weight\": 6, \"capacity\": 7})\n",
    "            ]\n",
    "\n",
    "my_graph.add_edges_from(my_edges)\n",
    "\n",
    "# Add several nodes with same weight and capacity:\n",
    "my_graph.add_edges_from([(5,4), (5, 2), (5, 3)], weight=5, capacity= 9)\n",
    "\n",
    "# Draw with spring layout\n",
    "nx.draw_spring(my_graph, with_labels=True)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Adding paths from lists\n",
    "It is also possible to add paths to a graph using an array that contains the list of nodes in the path.\n",
    "If the nodes do not exist in the graph, they are automatically added. It is possible to define properties for the edges\n",
    "added to the path. let us see it in action:"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "my_graph = nx.DiGraph()\n",
    "\n",
    "path_1 = [1, 2, 3, 4]\n",
    "# Add a path 1 -> 2 -> 3 4 with weight 3\n",
    "nx.add_path(my_graph, path_1, weight = 3)\n",
    "\n",
    "# Add a reverse path with weight 4\n",
    "path_2 = [4, 3, 2, 1]\n",
    "nx.add_path(my_graph, path_2, weight = 4)\n",
    "\n",
    "nx.draw_planar(my_graph)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Adding cycles from list\n",
    "The function ```add_cycle``` adds a cycle connecting the nodes provided in an array. It is similar to ```add_path```, \n",
    "except that the first and the last node are connected: \n",
    "\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "my_graph = nx.DiGraph()\n",
    "\n",
    "path_1 = [1, 2, 3, 4]\n",
    "# Add a path 1 -> 2 -> 3 4 with weight 3\n",
    "nx.add_cycle(my_graph, path_1, weight = 3)\n",
    "\n",
    "nx.draw_planar(my_graph)\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Creating graphs from Pandas dataframes\n",
    "#### from_pandas_edgelist\n",
    "Networkx has a good integration with [Pandas](https://pandas.pydata.org/). The function ```from_pandas_edgelist``` \n",
    "creates a graph from a Pandas dataframe that contains the information of the edges. You only need to specify which column\n",
    "specifies the origin node, the destination node and which columns contain information about the edges we want to map as \n",
    "attributes. The arguments are:\n",
    "\n",
    "- edgelist: The dataframe containing the edge information\n",
    "- source: The column that contains the source nodes\n",
    "- Target: The column that contains the target nodes\n",
    "- edge_attr: An array with the names of the columns that contain edge attributes\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "edge_df = pd.DataFrame({'u': [1, 2, 2, 3, 3, 4], 'v': [2, 3, 4, 1, 4, 1], 'weight': [2, 1, 3, 4, 2, 1]})\n",
    "\n",
    "# Create a graph from the edge list\n",
    "graph = nx.from_pandas_edgelist(edge_df, 'u', 'v', ['weight'])\n",
    "\n",
    "nx.draw_planar(graph)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### from_pandas_adjacency_matrix\n",
    "It is also possible to create a graph from a Pandas dataframe that contains the adjacency matrix. An entry i,j in the \n",
    " dataframe corresponds to the weight of an edge from node i to j. For directed graphs, it is necessary to use the ```create_using``` argument equal to ```nx.Digraph```:"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "adjacency_matrix = pd.DataFrame([[0, 1, 0, 4, 0, 3], \n",
    "                                 [1, 0, 1, 0, 0, 7],\n",
    "                                 [0, 0, 0, 1, 0, 8],\n",
    "                                 [8, 0, 2, 0, 2, 5], \n",
    "                                 [9, 0, 7, 2, 0, 1],\n",
    "                                 [0, 0, 0, 1, 0, 0]])\n",
    "\n",
    "graph = nx.from_pandas_adjacency(adjacency_matrix, create_using=nx.DiGraph)\n",
    "\n",
    "print(graph.nodes)\n",
    "print(graph.adj)\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Export data to Pandas dataframe\n",
    "The functions ```to_pandas_adjacency``` and ```to_pandas_edgelist``` export the information of the graph to dataframes, \n",
    "either as the adjacency matrix or as an edge list (make sure you run the cell above):"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "df = nx.to_pandas_edgelist(graph)\n",
    "df\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Creating networks from Open Street Maps data\n",
    "[osmnx](https://osmnx.readthedocs.io/en/stable/) is a really nice package that allows to create a map from Open Street \n",
    "Map data, which is a really nice resource in logistics applications.\n",
    "\n",
    "#### Installation\n",
    "Run the following script to install onsmnx if it is not installed in your system:"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "!apt-get -qq install -y libspatialindex-dev && pip install -q -U osmnx"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### Creating a map\n",
    "You can create a network from a map using three functions: \n",
    "\n",
    "- ```graph_from_place```: Creates a network map from a search query to Open Street Maps. For instance, the query ```'Valencia, VC, Spain'```\n",
    " returns a network of the street map of the city of Valencia. There are some requirements to build these queries, and if\n",
    " it does not work in your app, you can use any of the other two methods described in this section.\n",
    "- ```graph_from_address```: Creates a network map centered  providing an address. The argument ```address``` specifies \n",
    "the address to geocode and use as the central point around which the graph is constructed. The argument ```dist``` \n",
    "specifies the maximum distance from the center address to any node in the graph. \n",
    "- ```graph_from_bbox```: Creates a graph within four points of a bounding box, specifying the ```north``` northern \n",
    "latitude of the bounding box, the ```south``` southern latitude of bounding box, the ```east``` eastern longitude of \n",
    "the bounding box and the ```west``` western longitude of the bounding box."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import osmnx as ox\n",
    "# get two markers from Google Maps around EDEM\n",
    "# Latitude, Longitude\n",
    "#North-west marker\n",
    "# 39.468370277652426, -0.33528989341188187\n",
    "# South east marker\n",
    "# 39.45963084307057, -0.3184406656568226\n",
    "G_nx = ox.graph_from_bbox(north=39.468370277652426, \n",
    "                          south=39.45963084307057, \n",
    "                          east=-0.3184406656568226, \n",
    "                          west=-0.33528989341188187)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### Rendering the map\n",
    "The function plot_graph_folium uses [Folium](https://python-visualization.github.io/folium/) to render the map in an \n",
    "interactive map:"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "m1 = ox.plot_graph_folium(G_nx)\n",
    "m1"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### get_nearest_node\n",
    "When you work on a graph, you can possibly click on a point in the map that is not necessarily an edge in the graph, so \n",
    "to be able to process it, you first need to find the node in the graph that is closest to the point. You can use the \n",
    "get_nearest_point function for this purpose, it returns the node that is closest to the point you pass as an argument so \n",
    "that you can later use the algorithms:"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "edem = (39.46211739713285, -0.3288013882525529)\n",
    "nearest_node = ox.get_nearest_node(G_nx, edem)\n",
    "nearest_node"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% \n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### Networkx algorithms\n",
    "You can now run any algorithm on your graph. The following example shows the spanning tree in green. Since spanning tree returns a graph, we can use again the function ```plot_graph_folium``` to render the result. Since we want to show it over the previous generated graph, we pass the Folium map object ```m1``` created below as the value of the named parameter graph_map, and we use the edge_color red to represent the edges of the spanning tree in a different color.\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "spanning_tree = nx.minimum_spanning_tree(G_nx.to_undirected())\n",
    "ox.plot_graph_folium(spanning_tree, graph_map=m1, edge_color='#ff0000')"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "#### plot route\n",
    "You can plot a route in a map using the function plot_route(). Optionally, you can pass as argument a previously generated map so that the route is printed as an overlay:"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "edem = (39.46211739713285, -0.3288013882525529)\n",
    "museum = (39.46329739674903, -0.33194815644130443)\n",
    "edem_nearest = ox.get_nearest_node(G_nx, edem)\n",
    "museum_nearest = ox.get_nearest_node(G_nx, museum)\n",
    "route = nx.shortest_path(G_nx, edem_nearest, museum_nearest)\n",
    "ox.plot_route_folium(G_nx, route, route_map=m1, weight=7)"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [],
   "metadata": {
    "collapsed": false
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.1"
  },
  "pycharm": {
   "stem_cell": {
    "cell_type": "raw",
    "source": [],
    "metadata": {
     "collapsed": false
    }
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}